#include "ArbolHuffman.h"
#include <iostream>

using namespace std;

ArbolHuffman::ArbolHuffman(string cadena) {
	this->nyt = new NodoArbolHuffman(0, 514, 1023); // Nodo NYT de frecuencia 0
	this->raiz = this->nyt;
	this->cadena = cadena;

	this->nodosOrdenados = new ListaDeNodosOrdenados();
	this->nodosOrdenados->agregarNodo(this->raiz);
	this->actualizarCaracterNuevo(257);
	//this->nodosOrdenados->agregarNodo(new NodoArbolHuffman(0,514,(unsigned int)EOF));
}
ArbolHuffman::ArbolHuffman() {
	this->nyt = new NodoArbolHuffman(0, 514, 1023); // Nodo NYT de frecuencia 0
	this->raiz = this->nyt;

	this->nodosOrdenados = new ListaDeNodosOrdenados();
	this->nodosOrdenados->agregarNodo(this->raiz);
	this->actualizarCaracterNuevo(257);
	//this->nodosOrdenados->agregarNodo(new NodoArbolHuffman(0,514,(unsigned int)EOF));
}

void ArbolHuffman::emitirEOF()
{
    this->codificarCaracter(257);
}

// Recibe un caracter y emite su código. Actualiza el arbol
unsigned int ArbolHuffman::codificarCaracter(unsigned int caracter) {
	//cout << "Leo caracter '"<<(char)caracter<<"(" << caracter << ")'." << endl;
	// Busco en nodosOrdenados pero tambien se podria buscar en el arbol
	NodoArbolHuffman* nodoConCaracter = 0;
	if ((nodoConCaracter = this->nodosOrdenados->buscarCaracter(caracter)) != 0)
	{
		this->enviarCodigo(nodoConCaracter);
		this->actualizar(nodoConCaracter);


	} else {
		//cout << "Es la primera vez que aparece '" << caracter << "'." << endl;
		//cout << "Envio codigo NYT:" << endl;
		this->enviarCodigo(this->nyt);
		//cout << "Envio caracter sin codificar: '" << caracter << "'." << endl;
		this->actualizarCaracterNuevo(caracter);

		bitset<8*sizeof(char)> bitSet = caracter;
		for (int i = 7; i >= 0; i--) {
			punteroHandlerOutput->siguienteBitEsUno(bitSet[i]);
			// << bitSet[i];
		}
		//cout << endl;
		//cout << bitSet << endl;

	}
	return 0; //TODO: Esto tiene que devolver el codigo del caracter
}

// Recibe un bit y devuelve un caracter si llegó a una hoja del árbol.
// En caso contrario, devuelve 0 (null).
unsigned char ArbolHuffman::decodificarCaracter() {

		NodoArbolHuffman* nodoActual = this->raiz;
		unsigned char caracterSalida = 0x00;
		//
		while ((nodoActual != this->nyt) && ((nodoActual->getHijoDerecha() != 0)||(nodoActual->getHijoIzquierda() != 0)) && (!punteroHandlerInput->eof())) {
			// Mientras estemos en un nodo interno nos movemos hacia las hojas...
			if (punteroHandlerInput->siguienteBitEsUno()) {
				//cout << "1" << endl;
				nodoActual = nodoActual->getHijoDerecha();
				//cout << "if (punteroHandlerInput->siguienteBitEsUno())" << endl;
			} else {
				nodoActual = nodoActual->getHijoIzquierda();
				//cout << "else" << endl;

			}
		}
		if(nodoActual->getCaracter()==257)
			{
			    punteroHandlerInput->setEof();
                return 0;
			}
		//como se le pide bits al handler en el while anterior, puede salir de ahi en oef...
		if (!punteroHandlerInput->eof()){
			if (nodoActual == this->nyt) {
				// Tengo que devolver el caracter sin comprimir
				// Agarro 8 bytes que representan bits en binario y los convierto a un byte
				for (int i = 8; i > 0; i--) {
					if (punteroHandlerInput->siguienteBitEsUno()) {
						caracterSalida = caracterSalida | (0x01 << (i-1));
					}

				}
				this->actualizarCaracterNuevo(caracterSalida);
			} else {
				caracterSalida = nodoActual->getCaracter();
				this->actualizar(nodoActual);
			}
		//cout << "Caracter decodificado: \"" << nodoActual->getCaracter() <<"\""<< endl;
		}
		return caracterSalida;

}


// Recorre el arbol desde la raiz hasta el nodo y manda el código (al reves).
void ArbolHuffman::enviarCodigo(NodoArbolHuffman* nodo) {
	string codigoRevertido = "";
	int contador = -1;
	bitset<32*sizeof(int)> bitSet;//problemas si tenemos un codigo mayor a 32 bits

	if (nodo != this->raiz) {
		do {
			contador++;
			if (nodo->getPadre()->getHijoDerecha() == nodo) {
				bitSet[contador] = 1;
				codigoRevertido += "1";
			} else {
				bitSet[contador] = 0;
				codigoRevertido += "0";
			}
			nodo = nodo->getPadre();
		} while (nodo != this->raiz);
	}

	//para poder invertir el codigo
	for (contador; contador >= 0; contador--) {
		punteroHandlerOutput->siguienteBitEsUno(bitSet[contador]);
		//cout << bitSet[contador] << endl;

	}
	// Doy vuelta el string
	string codigo = "";
	for (string::reverse_iterator rit = codigoRevertido.rbegin(); rit < codigoRevertido.rend(); rit++) {
		codigo += *rit;
	}
	// De alguna manera hay que hacer que este codigo se transforme en 1s y 0s en bits.
	//cout << "Codigo: " << codigo << endl;
}

// Agrega un nuevo caracter al arbol. Deja el arbol valido.
void ArbolHuffman::agregarCaracter(unsigned int caracter) {
	// Creo dos hojas (la del nuevo caracter y la del nuevo NYT)
	// cuyo padre es el viejo nodo NYT
	//cout << "Agrego '"<< caracter << "' al arbol." << endl;
	this->nyt->setHijoIzquierda(new NodoArbolHuffman(this->nyt, this->nyt->getNumero()-2, 1024));
	this->nyt->setHijoDerecha(new NodoArbolHuffman(this->nyt, this->nyt->getNumero()-1, caracter));
	this->nodosOrdenados->agregarNodo(this->nyt->getHijoDerecha());
	this->nodosOrdenados->agregarNodo(this->nyt->getHijoIzquierda());
	this->nyt->incrementarFrecuencia();
	this->nyt->getHijoDerecha()->incrementarFrecuencia();
	this->nyt = this->nyt->getHijoIzquierda();
}

// Actualiza el árbol a partir del caracter NYT
// Deja el arbol en un estado valido (Sibling property)
void ArbolHuffman::actualizarCaracterNuevo(unsigned int caracter) {
	this->agregarCaracter(caracter);
	NodoArbolHuffman* nodo = this->nyt->getPadre(); // NYT anterior
	while (nodo != this->raiz) {
		nodo = nodo->getPadre();
		NodoArbolHuffman* nodoMaxFrecuenciaEnBloque = this->nodosOrdenados->buscarMaxEnBloque(nodo->getFrecuencia());
		if ((nodoMaxFrecuenciaEnBloque != nodo) && (nodoMaxFrecuenciaEnBloque != nodo->getPadre())) {
			// Intercambio de nodos para poder incrementar la frecuencia luego
			// y que siga cumpliendo con la Sibling Property
			this->intercambiarNodos(nodo, nodoMaxFrecuenciaEnBloque);
		}
		nodo->incrementarFrecuencia();
	}
}

// Actualiza el árbol a partir de un nodo al que hay que incrementarle su frecuencia
// Deja el arbol en un estado valido (Sibling property)
void ArbolHuffman::actualizar(NodoArbolHuffman* nodo) {
	NodoArbolHuffman* nodoMaxFrecuenciaEnBloque = this->nodosOrdenados->buscarMaxEnBloque(nodo->getFrecuencia());
	if ((nodoMaxFrecuenciaEnBloque != nodo) && (nodoMaxFrecuenciaEnBloque != nodo->getPadre())) {
		// Intercambio de nodos para poder incrementar la frecuencia luego
		// y que siga cumpliendo con la Sibling Property
		this->intercambiarNodos(nodo, nodoMaxFrecuenciaEnBloque);
	}
	nodo->incrementarFrecuencia();
	while (nodo != this->raiz) {
		nodo = nodo->getPadre();
		NodoArbolHuffman* nodoMaxFrecuenciaEnBloque = this->nodosOrdenados->buscarMaxEnBloque(nodo->getFrecuencia());
		if ((nodoMaxFrecuenciaEnBloque != nodo) && (nodoMaxFrecuenciaEnBloque != nodo->getPadre())) {
			// Intercambio de nodos para poder incrementar la frecuencia luego
			// y que siga cumpliendo con la Sibling Property
			this->intercambiarNodos(nodo, nodoMaxFrecuenciaEnBloque);
		}
		nodo->incrementarFrecuencia();
	}
};

// Intercambia dos nodos de igual frecuencia
void ArbolHuffman::intercambiarNodos(NodoArbolHuffman* nodo, NodoArbolHuffman* nodoMaximo) {
	this->nodosOrdenados->intercambiarNodos(nodo->getNumero(), nodoMaximo->getNumero());
	NodoArbolHuffman* nodoPadre;
	nodoPadre = nodo->getPadre();
	NodoArbolHuffman* nodoPadreMaximo;
	nodoPadreMaximo = nodoMaximo->getPadre();
	if (nodoPadre->getHijoIzquierda() == nodo)
	{
		nodoPadre->setHijoIzquierda(nodoMaximo);
	} else {
		nodoPadre->setHijoDerecha(nodoMaximo);
	}
	nodoMaximo->setPadre(nodoPadre);
	if (nodoPadreMaximo->getHijoDerecha() == nodoMaximo) {
		nodoPadreMaximo->setHijoDerecha(nodo);
	} else {
		nodoPadreMaximo->setHijoIzquierda(nodo);
	}
	nodo->setPadre(nodoPadreMaximo);
	// Ahora quiero intercambiar los numeros de los nodos
	unsigned int numeroTemp = nodo->getNumero();
	nodo->setNumero(nodoMaximo->getNumero());
	nodoMaximo->setNumero(numeroTemp);
}
void ArbolHuffman::setBitHandlerInput(BitHandlerInput& bhi) {
	punteroHandlerInput = &bhi;
}

void ArbolHuffman::setBitHandlerOutput(BitHandlerOutput& bho) {
	punteroHandlerOutput = &bho;
}


void pruebasInput() {

	BitHandlerInput bhi("hola.huff",0);

	ArbolHuffman* arbol = new ArbolHuffman();
	arbol->setBitHandlerInput(bhi);

    ofstream archsal;
    archsal.open("resultado.txt",ios::binary);

	while (!bhi.eof()&&!bhi.eofVirtual())
	{
	    char c=arbol->decodificarCaracter();
	    if(!bhi.eofVirtual())
            archsal<<c;
	}

}

void pruebasOutput() {
	ifstream archEntrada("hola.txt",ios::binary);
	BitHandlerOutput bho("hola.huff",ios_base::out);
	ArbolHuffman* arbol2 = new ArbolHuffman();
	arbol2->setBitHandlerOutput(bho);
	unsigned int charActual = (unsigned int)archEntrada.get();
	while (!archEntrada.eof()) {
		arbol2->codificarCaracter(charActual);
		charActual = (unsigned int)archEntrada.get();
		//cout << "*****************************************************while" << endl;
	}
	arbol2->emitirEOF();
	bho.rellenarConCeros();
	bho.cerrarArchivo();
	//string holaaaaa = "01101000 0 01101111 00 01101100 100 01100001 001 11 0 1";
	//string holaaaaa = "01101000 00110111 10001101 10010001 10000100 11101  000";3 ceros de relleno
//problema con los 3 bits de relleno!! cuando decodifica, piensa q es un codigo del arbol..
//posible solucion -> guardar la longitud del string antes de guardarlo...
}

/*int main() {
	// Este string es el codigo de "hola" en bytes, no bits.
	//string codificado = "01101000001101111000110110010001100001";


	pruebasOutput();
	//system("pause");
	pruebasInput();

	return 0;

}*/
